#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#define maxn 30
using namespace std;
int n, m, v[maxn], w[maxn], dp[30005][maxn];
/**
 *  dp[i,j]表示 在允许花费代价为i的情况下,从1...j中挑选物品得到的最大满意度。 
 *  dp[i,j] = max{dp[i,j-1],dp[i-v[j],j-1]+v[j]*w[j]};
 */
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> v[i] >> w[i];
    }
    for (int j = 1; j <= m; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            dp[i][j] = dp[i][j-1];
            if (i > v[j])
                dp[i][j] = max(dp[i][j - 1], dp[i - v[j]][j - 1] + v[j] * w[j]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
};